package leetcode_二叉树;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 二叉搜索树中第 K 小的元素
 * 算法：树  中序遍历
 *
 * @author yzh
 * @version 1.0
 * @date 2021/9/13 16:03
 */
public class _230 {
    public static void main(String[] args) {
        // 5,3,6,2,4,null,null,1
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3, new TreeNode(2, new TreeNode(1, null, null), null), new TreeNode(4, null, null));
        root.right = new TreeNode(6, null, null);
        new _230().kthSmallest_recursion(root, 3);

    }

    public int kthSmallest_recursion(TreeNode root, int _k) {
        k = _k;
        return dfs(root);
    }

    int k;

    int dfs(TreeNode node) {
        if (node == null) return -1;
        int res = dfs(node.left);
        if (res != -1) return res;
        if (--k == 0) return node.val;
        return dfs(node.right);
    }

    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (--k == 0) return root.val;
            root = root.right;
        }
    }

}
